#include <bits/stdc++.h>
using namespace std;
#define N 10
int t[N][N];
int n, m;
void preorder(int root) //先序遍历以root为根的树
{
    printf("%d",root);
    for(int i=1;i<=n;++i)
        if(t[root][i]==1) preorder(i);
}

void lastorder(int root) //后序遍历以root为根的树
{
    for(int i=1;i<=n;++i)
        if(t[root][i]==1) lastorder(i);
    printf("%d",root);
}

int main()
{
    int x,y;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        t[x][y]=1;
    }
    preorder(4); cout<<endl;
    lastorder(4); cout<<endl;
    return 0;
}
